Luca Dall’Ava, 29th of September 2025

Aim of the talk: Present the main ideas behind the seminal Forking Lemma and its application to folding schemes

Table of contents

An (informal) introduction

The Forking Lemma was first introduced by Pointcheval and Stern in order to prove the security for Schnorr signatures in 1996.

Main idea: “We need a reduction”!

Analogy:

The Forking Lemma is a powerful, standardized technique for building these reductions, especially for schemes that use hash functions.

The model the Forking Lemma works in is the Random Oracle Model (ROM).

Recall that:

• In this model, we replace standard cryptographic hash functions (like SHA-256/Poseidon/Keccak256) with a perfect, publicly accessible random function—an "oracle."

• Any party can query the oracle with an input $x$, and it will return a truly random value $H(x)$, consistently providing the same output for the same input.

The key advantage for a security proof is that the entity performing the reduction (the "challenger") can program the oracle, observing the adversary's queries and controlling its responses. The Forking Lemma builds on exploiting this control.

The original Forking Lemma

The Forking Lemma is essentially a structured way to "rewind" a probabilistic adversary.

Intuition

Imagine an adversary, $\mathcal{A}$ , that takes a public key as input and, after some computation that includes making queries to a random oracle, outputs a valid digital signature forgery.

1. First Execution: We run the adversary's algorithm.
   1. $\mathcal{A}$ makes a query to the random oracle, say $q_1$.
   2. We, as the challenger, answer these with the random value $h_1$.
   3. The adversary eventually succeeds, producing a valid signature $σ_1$ for a message $m$. This signature is valid with respect to the hash outputs it received.

2. The "Fork": What if we could turn back time?
   1. We "rewind" the adversary's program to the exact moment before it queried $q_1$ and received $h_1$.

      Note: We have its exact memory state, its program counter, everything!

3. Second Execution:
   1. We resume the adversary from this saved state.
   2. $\mathcal{A}$ proceeds to make the same query, $q_1$. This time, however, we provide a different, fresh random value $h_2$ as the response.
   3. (From this point forward, we continue answering any subsequent queries with new random values.)

4. Output:
   1. With some non-negligible probability, the adversary, if it is robust, will succeed again and produce a second valid signature, $σ_2$.

The Payoff

We are now in possession of two valid signatures, $σ_1$ and $σ_2$, that are related in a very specific way: they only differ because of the hash outputs, $h_1$ and $h_2$. They share the same initial computation path but diverge at a controlled point due to our intervention with the random oracle.

This often yields a system of algebraic equations that can be solved to extract a secret (key), thereby breaking the underlying hard problem.

Classic Example: Breaking Schnorr Signature

Let's see how this works with the Schnorr signature scheme.

• Setting: A cyclic group $\mathbb{G}$ of prime order $p$ with generator $G$.

• Secret Key: An integer $x∈\{1,…,p−1\}$.

• Public Key: $P=x⋅G$ (where $x$ is the secret key)

• Signature on message $m$:
  1. Choose a random nonce $k$, compute $R=k⋅G$.
  2. Compute the hash challenge $h=H(m||R)$.
  3. Compute $s=k+h⋅x$.
  4. The signature is the pair $(R,s)$.

• Verification Equation: $s⋅G=R+H(m||R)⋅P$.

Security Reduction using the Forking Lemma:

Assume an adversary $\mathcal{A}$ can forge a Schnorr signature.

1. First iteration:

   An adversary $\mathcal{A}$ produces a valid forgery $(R,s_1)$. This means it must have queried the oracle for $H(m∥R)$ to get a hash $h_1$.

   We obtain $s_1⋅G=R+h_1⋅P$

2. (Fork):
   1. We rewind $\mathcal{A}$ to before it got $h_1$, and give it a new hash $h_2$ instead.
   2. With some probability, it succeeds again, producing $(R,s_2)$.
   3. Now, we obtain: $s_2⋅G=R+h_2⋅P$

3. Solving for the Secret:
   1. We have a system of two linear equations:

      $$s_1⋅G=R+h_1⋅P, \quad s_2⋅G=R+h_2⋅P.$$

   2. Subtracting them gives: $(s_1−s_2)⋅G=(h_1−h_2)⋅P$
   3. Since $P=x⋅G$, we can rewrite this as:$(s_1−s_2)⋅G=(h_1−h_2)⋅x⋅G$
   4. We can now easily solve for the secret key

   $$x=(s_1−s_2)(h_1−h_2)^{-1}\pmod p .$$

4. Conclusion:

   The ability to forge a Schnorr signature allows us to solve the discrete logarithm problem. Therefore, the scheme is secure.

We can think of this algorithm as of an Extractor which outputs the secret key.

The Forking Lemma for folding schemes

Recalls on Folding Schemes (Informal)

A folding scheme is a cryptographic primitive that takes two instances of a problem (for example, two R1CS/CCS instances) and folds them into a single, combined instance.

The key property is that the folded instance is satisfiable, that is, has a valid witness, if both original instances were satisfiable.

We can represent it as the following map:

• At each step, the prover doesn't generate a full, expensive proof. Instead, they use a lightweight cryptographic protocol to fold the claim of the current step's correctness into a running accumulator.

• A single, final SNARK is only generated at the very end to prove the correctness of the entire folded accumulation.

A naive take on extraction

We have seen that “the folded instance is satisfiable, that is, has a valid witness, if both original instances were satisfiable”, but

In a folding scheme, the witnesses from two separate instances $(W_1,W_2)$ are algebraically combined using the verifier's random challenge $r$ to create a new, single folded witness:

Let’s give it a try!

• The extractor is left with two valid equations, but they don't share the same unknowns. It's like having:

  $$z₁ = x₁ + r₁ \cdot y₁,\\ z₂ = x₂ + r₂ \cdot y₂.$$

  You have two equations, but four unknowns! You can't solve this system for the original witnesses $(W_1,W_2)$.

A modified Forking Lemma

The proof for folding schemes is a two-step process that adapts the classic lemma.

The Key Insight: The folded witness isn't just a random value; it's an algebraic polynomial of the verifier's random challenge, $r$. The original witnesses we want to find are the coefficients of this polynomial.

• Therefore, the modern proof strategy becomes:
  1. Use the Forking Lemma to get the raw data we need (the tree of transcripts).
  2. Use algebra to reconstruct the polynomial and extract its coefficients (the witnesses).

The Two-Step Proof Strategy

The process is as follows.

Part 1: The Forking Lemma's Role (The "Meta-Theorem")

Part 2: The Tree-Based Extractor's Job (The "Worker")

The Extractor

Let’s look at how $Ext_{tree}$ uses its input to find the witnesses (in the simplified version of a Nova-like folding scheme).

Conclusion: Take-home message

• The Forking Lemma is a foundational and flexible tool for proving security.

• For modern primitives like folding schemes, it has been adapted to a new, powerful technique.

• By combining the classic rewinding argument with algebraic interpolation, we can prove knowledge soundness even for complex, compositional protocols built from folding schemes (but also, more generally, reductions of knowledge).

References

• [K23] - Komlo, C. - A Note on Various Forking Lemmas, https://www.chelseakomlo.com/assets/content/notes/Forking-Lemma-Variants.pdf

• [KP22] - Abhiram Kothapalli, Bryan Parno, "Algebraic Reductions of Knowledge," Cryptology ePrint Archive, 2022, https://eprint.iacr.org/2022/009

• [KST22] - Kothapalli, A., Setty, S., Tzialla, I.: Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. In: CRYPTO (2022)

• [PS96] - Pointcheval, D., and Stern, J. (1996). - "Security Proofs for Signature Schemes." In Proceedings of the 15th Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT '96).